package com.atzxh.datastructure.LinkedList;

/**
 * @author 小红同学
 * @create 2022-09-29-19:04
 * @description  单链表
 */

/**
 * 小结:
 *      1)链表是以节点的方式来存储,是链式存储
 *      2)每个节点包含data域， next域:指向下一个节点.
 *      3)如图:发现链表的各个节点不一定是连续存储.
 *      4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
 */
public class SingleLinkedListTest {

    public static void main(String[] args) {
        //测试

        //1.创建节点
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "林冲");
        HeroNode node3 = new HeroNode(3, "吴用");
        HeroNode node4 = new HeroNode(4, "李逵");

        //2.创建单链表，把节点添加进去
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(node1);
//        singleLinkedList.add(node2);
//        singleLinkedList.add(node3);
//        singleLinkedList.add(node4);

        singleLinkedList.addOrderByNo(node1);
        singleLinkedList.addOrderByNo(node4);
        singleLinkedList.addOrderByNo(node3);
        singleLinkedList.addOrderByNo(node2);

        //3.遍历链表
        singleLinkedList.list();

    }

}
//定义一个单链表，管理节点
class SingleLinkedList{
    //定义一个头节点
    private HeroNode head = new HeroNode();

    

    //不考虑排序
    public void add(HeroNode heroNode){

        HeroNode temp = head;

        while (true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }

        temp.next = heroNode;
    }

    //按照no由小到大顺序添加
    public void addOrderByNo(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;   //添加数据的no是否存在

        //通过循环遍历来找出插入位置
        while (true){
            if (temp.next == null){
                break;
            }
            if(temp.next.no > heroNode.no){     //找到插入位置
                break;
            }else if (temp.next.no == heroNode.no){
                flag = true;//说明编号已经存在
                break;
            }
            //temp后移
            temp = temp.next;
        }

        if(flag){
            System.out.println("插入的数据有误！！！编号已存在");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //遍历
    public void list(){

        if(head.next == null){
            System.out.println("链表为空！！！");
            return;
        }

        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }

            System.out.println(temp);
            temp = temp.next;
        }
    }
}
//定义节点
class HeroNode {
    public int no;
    public String name;
    public HeroNode next;

    public HeroNode() {
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}